// NC133 链表的奇偶重排
// https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
// 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
// 注意是节点的编号而非节点的数值。
// 输入：{1,4,6,3,7}
// 返回值：{1,6,7,4,3}
// 说明：
// 1->4->6->3->7->NULL
// 重排后为
// 1->6->7->4->3->NULL
// 奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

#include <deque>
#include <iostream>
using namespace std;

struct ListNode {
  int val;
  struct ListNode* next;
  ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
 public:
  ListNode* oddEvenList(ListNode* head) {
    // write code here
    deque<ListNode*> deqNode1;
    deque<ListNode*> deqNode2;
    while (head) {
      deqNode1.push_back(head);
      head = head->next;
      if (head == nullptr) break;
      deqNode2.push_back(head);
      head = head->next;
    }
    ListNode* resHead = new ListNode(0);
    ListNode* lastNode = resHead;
    while (!deqNode1.empty()) {
      ListNode* t = deqNode1.front();
      printf("%d,", t->val);
      deqNode1.pop_front();
      lastNode->next = t;
      lastNode = t;
      t->next = nullptr;
    }
    while (!deqNode2.empty()) {
      ListNode* t = deqNode2.front();
      printf("%d,", t->val);
      deqNode2.pop_front();
      lastNode->next = t;
      lastNode = t;
      t->next = nullptr;
    }
    return resHead->next;
  }
};

// 方法2 .java
// ListNode oddEvenList (ListNode head) {
//   // write code here
//   if(head == nullptr || head.next == nullptr) return head;
//   ListNode evenHead = head.next;
//   ListNode odd = head,even = head.next;
//   while(even != null && even.next != null){
//     odd.next = even.next;
//     odd = odd.next;
//     even.next = odd.next;
//     even = even.next;
//   }
//   odd.next = evenHead;
//   return head;
// }
